package 排序;

/**
 * @Author Weton Li
 * @Date 2021/4/8 13:34
 */
public class 插入排序 {


    public static void insertSort(int[] nums) {

        int n = nums.length;

        for (int i = 0; i < n - 1; i++) {

            int currNum = nums[i + 1]; // 初始当前数为第二个数
            int prev = i;

            while (prev >= 0 && currNum < nums[prev]) { // 如果当前数大于前一个数，则停止寻找位置
                nums[prev + 1] = nums[prev];
                prev--;
            }
            nums[prev + 1] = currNum;
        }
    }


    public static void main(String[] args) {
        int[] input = {1, 9, 3, 5, 4, 1, 4, 5, 7, 5};
        insertSort(input);
        for (int i : input) {
            System.out.print(i + "\t");
        }
    }
}
